/**
 * 剑指 Offer 47. 礼物的最大价值
 * https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
 */
public class Solutions_Offer_47 {
    public static void main(String[] args) {
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};  // output: 12 {1, 3, 5, 2, 1}
        int result = maxValue(grid);

        System.out.println(result);
    }

    public static int maxValue(int[][] grid) {
        if (grid == null || grid.length < 1 || grid[0].length < 1) {
            return 0;
        }
        int m = grid.length, n = grid[0].length;
        // 动态规划数组
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 比较当前遍历元素的上一元素与前一元素，取较大值
                int max = Math.max(dp[i - 1][j], dp[i][j - 1]);
                // 根据较大值来判断，是取左边的，还是取上边的
                dp[i][j] = grid[i - 1][j - 1] + max;
            }
        }
        return dp[m][n];
    }
}
